In modern computing systems, it is often desirable to limit access to electronic content or processing resources, or to allow only certain parties to perform certain actions. A number of techniques have been used or proposed for enabling such control. One set of techniques makes use of digital certificates. A digital certificate can be viewed as an authorization to perform an action or to access a resource. An entity may possess numerous certificates. In order to determine whether an entity is authorized to perform an action, one looks at the certificates in the entity's possession, and determines whether authorization has been granted. Because authorization may be implicit or delegated (e.g., one entity may authorize another entity to issue authorizations on its behalf), it is often necessary to evaluate multiple certificates to determine whether a request for system resources should be granted.
Trust management systems define languages for expressing authorizations and access control policies, and provide trust management engines for determining when a particular request is authorized. The task of the trust management engine will typically involve evaluating both the request and a set of certificates associated with the request and/or the requestor. In some conventional trust management systems, the trust management engine makes decisions using a process similar to that shown in FIG. 1. As shown in FIG. 1, trust management engine 102 accepts a request 104 to perform an action or to access a resource. The trust management engine also accepts a set of certificates 106 associated with the requestor or the request, and some indication 108 of the identity of the owner or “root” associated with the requested resource (i.e., the authorizing principal from whom permission to access the resource must ultimately flow). Next, the trust management engine performs a certificate path discovery process 110 on the group of certificates 106 to determine the way in which the certificates should be arranged in order to facilitate the remainder of the trust management decision process. The result of certificate path discovery is an ordered list of certificates 112. The ordered list of certificates 112 is then reduced by successively combining adjacent certificates in the list 114. The end result of the reduction process is a certificate 116 representing the combination of each of the assertions expressed by the certificates in the original group. This certificate is then evaluated 118 to determine whether the original request should be granted or denied 120.
A problem with approaches such as the one shown in FIG. 1 is that the computation involved can be relatively costly.